#include "bits/stdc++.h"
using namespace std;
// O(1/4)次根号n求n的质因子
// 改成f128太慢建议只用long double
// 如果wa了去掉mul，直接用int128取模
namespace PollardRho {
  using ll = long long;
  using f64 = long double;
  vector<int> base{2, 325, 2047, 9375, 28178, 450775, 1373653, 9780504, 1795265022};
  struct Barret {
  	ll mul(ll a, ll b) {
  		ll z = a * invp * b + 0.5;
    	ll t = a * b - z * p;
  		return t + (t >> 63 & p);
  	}

  	ll pow_mod(ll a, ll b, ll ret = 1) {
  		for (; b > 0; b >>= 1, a = mul(a, a)) {
        if (b & 1) {
        	ret = mul(ret, a);
        }
      }
    	return ret;
  	}

  	void set_mod(ll x) {
  		p = x, invp = (f64)1 / x;
  	}

  	ll p;
  	f64 invp;
  } tool;

  bool miller_rabin(ll p) {
  	if (p == 1) {
  		return 0;
    }
    tool.set_mod(p); 
    ll d = __builtin_ctzll(p - 1), s = (p - 1) >> d;
    for (auto &a : base) {
      if (a % p == 0) {
      	continue;
      }
      ll x = tool.pow_mod(a,s), y;
      for (int i = 0; i < d; ++i, x = y) {
        y = tool.mul(x, x);
        if (y == 1 && x != 1 && x != p - 1) {
          return 0;	
        }
      }
      if (x != 1) {
      	return 0;
    	}
    }
    return 1;
  }

  ll rho(ll n) {
  	if (!(n & 1)) {
  		return 2;
    }
    ll x = 0, y = 0, prod = 1;
    auto f = [&](ll o) { 
    	return tool.mul(o, o) + 1;
    };
    tool.set_mod(n);
    for (int t = 30, z = 0; t % 64 || __gcd(prod, n) == 1; ++t) {
      if (x == y) {
      	x = ++z;
      	y = f(x);
      }
      if (ll q = tool.mul(prod, (x + n - y))) {
      	prod = q;
      }
      x = f(x), y = f(f(y));
    }
    return __gcd(prod, n);
  }

  vector<ll> get_factors(ll n) {
  	if (n == 1) {
  	  return {};
  	}
    vector<ll> pf;
    auto f = [&](auto &&f, ll x) {
      if (x == 1) {
      	return ;
      }
      if (miller_rabin(x)) {
      	pf.push_back(x);
      	return ;
      }
      ll y = rho(x);
      assert(x != y);
      f(f, y);
      f(f, x / y);
    };
    f(f, n);
    return pf;
  }
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int q;
	cin >> q;
	while (q--) {
		long long n;
		cin >> n;
		auto fac = PollardRho::get_factors(n);
		if (fac.size() <= 1) {
			cout << "Prime" << '\n';
		} else {
			cout << *max_element(fac.begin(), fac.end()) << '\n';
		}
	}
	return 0;
}